package com.leetcode.binarytree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * date:
 * description:
 */
public class CodecBFS {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null){
                sb.append(cur.val).append(",");
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                sb.append("null,");
            }
        }
        return sb.deleteCharAt(sb.length() - 1).toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if("null".equals(data)){
            return null;
        }
        String[] items = data.split(",");
    //        第一个不可能是null
        TreeNode root = new TreeNode(Integer.parseInt(items[0]));
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int index = 1;
        while(index < items.length){
            TreeNode cur = queue.poll();
            String left = items[index++];
            String right = items[index++];
            if(!"null".equals(left)){
                TreeNode lnode = new TreeNode(Integer.parseInt(left));
                cur.left = lnode;
                queue.offer(lnode);
            }
            if(!"null".equals(right)){
                TreeNode rnode = new TreeNode(Integer.parseInt(right));
                cur.right = rnode;
                queue.offer(rnode);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        String data = "1,2,3,null,null,4,5,null,null,null,null";
        CodecBFS ins = new CodecBFS();
        TreeNode root = ins.deserialize(data);
        String res = ins.serialize(root);
        System.out.println(res);
    }
}
